class Solution
{
public:
    int maximumScore(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<int> primeScores(n);

        for (int i = 0; i < n; ++i)
        {
            primeScores[i] = primeScore(nums[i]);
        }

        // 寻找每个primeScores左边第一个不小于它的位置和右边第一个严格大于它的位置
        stack<int> st;
        vector<int> left(n);
        for (int i = 0; i < n; ++i)
        {
            while (!st.empty() && primeScores[st.top()] < primeScores[i])
            {
                st.pop();
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
        st = stack<int>();
        vector<int> right(n);
        for (int i = n - 1; i >= 0; --i)
        {
            while (!st.empty() && primeScores[st.top()] <= primeScores[i])
            {
                st.pop();
            }
            right[i] = st.empty() ? n : st.top();
            st.push(i);
        }

        // 按照nums, 对索引从大到小排序
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int i, int j)
             { return nums[i] > nums[j]; });

        // 快速幂
        auto power = [&](long long a, long long b)
        {
            long long ans = 1;
            while (b)
            {
                if (b & 1)
                {
                    ans *= a;
                    ans %= 1000000007;
                }
                a *= a;
                a %= 1000000007;
                b >>= 1;
            }
            return ans;
        };

        long long ans = 1;
        for (int i = 0; i < n; ++i)
        {
            long long index = indices[i];
            long long count = (right[index] - index) * (index - left[index]);
            if (count >= k)
            {
                ans *= power(nums[index], k);
                ans %= 1000000007;
                break;
            }
            else
            {
                ans *= power(nums[index], count);
                ans %= 1000000007;
                k -= count;
            }
        }
        return ans;
    }

    int primeScore(long long n)
    {
        if (n <= 1)
        {
            return 0;
        }

        // 计算n的不同质因子的个数
        int score = 0;
        for (long long i = 2; i * i <= n; ++i)
        {
            if (n % i == 0)
            {
                ++score;
                while (n % i == 0)
                {
                    n /= i;
                }
            }
        }
        return score + (n > 1);
    }
};